%%%-------------------------------------------------------------------
%%% File    : p35.erl
%%% Author  : Plamen Dragozov <plamen at dragozov.com>
%%% Description : 
%%% The number, 197, is called a circular prime because all rotations 
%%% of the digits: 197, 971, and 719, are themselves prime.
%%%
%%% There are thirteen such primes below 100: 
%%% 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
%%%
%%% How many circular primes are there below one million?
%%%
%%% Created : 28 Dec 2008
%%%-------------------------------------------------------------------
-module(p35).

%% API
-compile(export_all).

%%====================================================================
%% API
%%====================================================================
%%--------------------------------------------------------------------
%% Function: 
%% Description:
%%--------------------------------------------------------------------
solution(Max) ->
    1 + test(3, Max, ets:new(lookup, []), [2]). 

%%====================================================================
%% Internal functions
%%====================================================================
%One of the rotations is picked as the lead(the smalles) and a table is used where all found prime leads are keys
%for the list of all theirr rotations which are not found to be prime (yet) and the total of the found prime rotations.
% In the end we just sum the totals for all leads that have empty lists of non-prime rotations (i.e. we found all their 
% rotations to be prime).
test(N, Max, Tbl, _) when N > Max ->
    ets:foldl(fun({_, Size, []}, Acc) -> 
                                 Size+Acc;
                            (_, Acc) -> Acc
              end, 
              0, 
              Tbl);
test(N, Max, Tbl, Primes) ->
    IsPrime = is_prime(N, math:sqrt(N), Primes),
    case IsPrime of 
        true -> 
            [Lead|Rotations] = rotations(N),          
            case Lead < pow10(N) of%when the number contains a 0, ignore it
                true ->
                    void;
                _->
                    case N =:= Lead of
                        true ->
                            Remaining = [R || R<-Rotations, R=/=N],
                            ets:insert(Tbl, {N, length(Remaining) + 1, Remaining});
                        _ ->
                            Prev = ets:lookup(Tbl, Lead),
                            case Prev of 
                                [] -> void;
                                [{Lead, Size, Rest}] -> 
                                    Remaining = [R || R<-Rest, R=/=N],
                                    %remove duplications
                                    ets:insert(Tbl, {Lead, Size - (length(Rest) - length(Remaining)) + 1, [R || R <- Rest, R =/= N]})
                            end
                    end
            end,
            test(N+2, Max, Tbl, Primes++[N]);
        _ -> 
            test(N+2, Max, Tbl, Primes)
    end.

% Returns a sorted list of all rotations of a number
rotations(N) ->
    Digits = to_digits(N),
    Size = array:size(Digits),
    lists:sort([from_digits(lists:foldl(fun(J, Acc) -> array:set((J + I) rem Size, array:get(J, Digits), Acc) end, array:new(Size), lists:seq(0, Size - 1)))|| I <- lists:seq(0, Size - 1)]).

%number to an array of digits
to_digits(N) ->
    to_digits(N, []).
to_digits(0, Acc) ->
    array:from_list(Acc);
to_digits(N, Acc) ->
    to_digits(N div 10, [N rem 10|Acc]).

%array of digits to a number
from_digits(Array) ->
    Size = array:size(Array),
    lists:foldl(fun(D, Acc) -> Acc*10 + array:get(D, Array) end, 0, lists:seq(0, Size-1)).

%Test if divisible by one of the previous primes.
%The list of primes has to be sorted in ascending order.
%We only need to check bellow or equal to sqrt(N)
is_prime(_, _, []) -> true;
is_prime(N, Sqrt, [H|T]) ->
    case (H > Sqrt) of
        true -> true;
        _ -> (N rem H =/= 0) andalso is_prime(N, Sqrt, T)
    end.


pow10(X) ->
    pow10(X, 1).

pow10(X, Acc) when X < 10 ->
    Acc;
pow10(X, Acc) ->
    pow10(X div 10, Acc * 10).
